//
// Description: 160. 相交链表
// Created by Loading on 2021/7/21.
//

#include <bits/stdc++.h>
#include "Data_Structure_Definition.h"

using namespace std;

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (!headA || !headB) {
        return nullptr;
    }
    ListNode *pA = headA;
    ListNode *pB = headB;
    // 双指针遍历，某一个链表遍历到结尾时，指向另一个链表的头
    // 两个节点相同时，即为相交节点，不相交时，两个节点均为空节点
    while (pA != pB) {
        pA = pA ? pA->next : headB;
        pB = pB ? pB->next : headA;
    }

    return pA;
}

int main() {
    auto *headA = new ListNode(1);
    headA->next = new ListNode(2);
    headA->next->next = new ListNode(3);
    headA->next->next->next = new ListNode(4);
    headA->next->next->next->next = new ListNode(5);
    headA->next->next->next->next->next = nullptr;

    auto *headB = new ListNode(7);
    headB->next = new ListNode(6);
    headB->next->next = headA->next->next->next;

    auto *result = getIntersectionNode(headA, headB);
    if (result) {
        cout << result->val << endl;
    } else {
        cout << "nullptr" << endl;
    }

}